package com.jack.leetcode.array;

/**
 * Created by zhang_j on 2020/7/10
 */
public class 下一个排列 {

    public static void main(String[] args) {
        int[] c = {1,2,3};
        nextPermutation(c);
        nextPermutation(c);
        nextPermutation(c);
        nextPermutation(c);
        nextPermutation(c);
        nextPermutation(c);
        nextPermutation(c);

        nextPermutation(new int[]{100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1});
    }

    public static void nextPermutation(int[] nums) {
        int n = nums.length;
        if(n == 1){
            return ;
        }
        if(nums[n-1] > nums[n-2]){
            swap(nums, n-1, n-2);
            return;
        }
        for(int i = n-1;i > 0;i--){
            if(nums[i] > nums[i-1]){
                int index = i+1;
                while(index < n && nums[index] > nums[i-1]){
                    index++;
                }
                swap(nums, index-1, i-1);
                reverse(nums, i, n-1);
                return;
            }
        }
        reverse(nums, 0, n-1);
    }

    private static void reverse(int[] nums, int begin, int end){
        int right = end;
        int left = begin;
        while(right > left){
            int tmp = nums[left];
            nums[left++] = nums[right];
            nums[right--] = tmp;
        }
    }

    private static void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
